Programmable logic devices (“PLDs”) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (“FPGA”), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (“IOBs”), configurable logic blocks (“CLBs”), dedicated random access memory blocks (“BRAMs”), multipliers, digital signal processing blocks (“DSPs”), processors, clock managers, delay lock loops (“DLLs”), and so forth. As used herein, “include” and “including” mean including without limitation.
One such FPGA is the Xilinx Virtex™ FPGA available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. Another type of PLD is the Complex Programmable Logic Device (“CPLD”). A CPLD includes two or more “function blocks” connected together and to input/output (“I/O”) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (“PLAs”) and Programmable Array Logic (“PAL”) devices. Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, for example, using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable.
For purposes of clarity, FPGAs are described below though other types of PLDs may be used. FPGAs may include one or more embedded microprocessors. For example, a microprocessor may be located in an area reserved for it, generally referred to as a “processor block.”
As is known, arithmetic coding (“AC”) may be used for an entropy encoder. In AC, each symbol to be encoded is assigned a probability of occurrence and a sub-range. Sub-ranges for each symbol follow from the assigned probability and the sequence of symbols. An initial range is set as being between 0 and 1. As each symbol is processed, an encoder restricts the range to a smaller interval than this initial interval responsive to the corresponding sub-range for the symbol. After a sub-range of an initial symbol is used to set a new range smaller than the initial range of 0 to 1, a sub-range for a next symbol further restricts the smaller range.
As is known, lower and upper bounds of sub-ranges indicate percentages of a range for setting a new more restricted range. For entropy encoding, conventionally a sequence of encoded symbols is reduced to a final sub-range value, which may be transmitted as a number of bits. Conventionally, this number of bits is represented in a fixed point notation.
Thus, AC assigns a fixed code length to a sequence of symbols based upon their probability of occurrence (“P”) as indicated above, where the fixed code length is represented by the number of bits used to express the final sub-range value for the sequence of symbols and has a bit length equivalent to log2(1/P). It should be understood that as the number of symbols in a sequence increases, the fractional number extends further to the right of a decimal point, for example. Accordingly, as the fractional number extends further to the right of the decimal point, more bits are used to encode the sequence of symbols.
Context Adaptive Binary Arithmetic Coding (“CABAC”) involves a similar encoding process as AC, but with the following differences. In CABAC, symbols to encode are single bit values, namely either a logic 1 or a logic 0. This is known as a “binary format,” and may be contrasted with a fractional value between 0 and 1 in AC. Thus, if a symbol is not in a binary format, it is binarized prior to encoding. Bits obtained from such binarization are referred to as “binarized bits,” “bins,” or “symbols,” and such symbols are sequentially encoded using CABAC.
For AC, a probability value assigned to a symbol is static; however, in CABAC dynamic probability values for symbols are used. By dynamic probabilities, it is meant that probability for a symbol is updated in each associated succeeding encoding pass. In CABAC, probability of a symbol may be estimated from its context information (“context”), and from previous probability(ies) of such symbol, if any, due to the iterative nature of dynamic probability values as previously described.
As previously indicated, in AC it is assumed that more bits may be added to represent a constricting sub-range value. However, in CABAC, the number of bits for specifying range (“RANGE”) is fixed. In CABAC, RANGE is bounded by a low value (“LOW” or “L”)) and a high value (“HIGH” or “H”). To adjust LOW and HIGH RANGE interval markers to meet the fixed bit restriction, normalization is used. During normalization, bits may be shifted out and be inserted into an output stream.
For a given context, a symbol is encoded as either a most probable symbol (“MPS”) or a least probable symbol (“LPS”). This distinction as between symbols is generally for having long strings of either a logic 0 or a logic 1 to enhance compression efficiency. Within a sub-range, probability of an LPS is given by PLPS. Likewise, within a sub-range, probability of an MPS is given as PMPS. Because PMPS equals probability of a symbol (“Psymbol”) minus PLPS, conventionally often only PLPS is used. Within a sub-range, CABAC defines two subintervals, namely an LPS RANGE (“RANGELPS”) which is equal to RANGE multiplied by PLPS, and an MPS RANGE (“RANGEMPS”) which is equal to RANGE minus RANGELPS.
FIG. 19 is a code listing depicting binary arithmetic encoding code listing 1900 of the prior art. Listing 1900 is part of a Joint Model (“JM”) source code reference as is known. JM reference software is a widely accepted reference point for developers of H.264 applications. The H.264 standard calls for CABAC for providing an entropy encoder. The output of CABAC is a compressed bitstream as specified by the ITU-T Video Coding Experts Group (“VCEG”) together with the ISO/IEC Moving Picture Experts Group (“MPEG”) as the product of a collective partnership effort known as the Joint Video Team (“JVT”). The collaborative effort is also known as H.264/AVC/MPEG4 Part 10.
Briefly, listing 1900 is for arithmetic encoding of one binary symbol by using a probability estimate of its associated context model. There are three main functions of listing 1900, namely to update the probability of a current symbol, to perform normalization of an encoding interval, and to insert “outstanding bits” into an output bitstream.
Pointer 1901 points to where the stream to be encoded is located. Only one bit is encoded at a time. Furthermore, it should be appreciated that normalization/renormalization (“normalization”) loop 1922 takes up to seven iterations to encode one bit. Input parameters to the function “biari_encode_symbol” are generally indicated by pointers 1901, 1902, and 1904. An “eep” pointer 1901 references a data structure of an encoded output stream. Pointers 1904 and 1902 reference the information for encoding, namely generally the symbol to encode and the associated context information, respectively. More particularly, the parameter “symbol” associated with pointer 1904 has two valid data states, either a logic 0 or a logic 1. Pointer 1904 indicates the bit to be encoded. If the value to encode is not in a binary format, it is first binarized prior to encoding.
After binarization, each resulting symbol is serially encoded. At each iteration, the function “birai_encode_symbol” is used. The parameter “bi_ct” is a pointer 1902 to a context information data structure for the symbol to be encoded. The context information data structure contains a state field and an MPS field. The state field is an index of assigned probability of a current symbol in the data structure, such as a probability table. The MPS field has either a logic 1 or a logic 0. The value of bi_ct state represents the probability of the current symbol to encode. The determination that the current symbol is the MPS forces a long string of logic 0s or logic 1s, depending which is set in the MPS field. Longer strings increase encoding efficiency.
As is known, for CABAC encoding, intervals are divided and thus there is a new RANGE and new LOW determined for encoding of each symbol. A symbol to encode 1904 has associated context information as indicated by pointer 1902. As generally indicated by arrow 1903, encoding interval boundaries described above are represented. Similar to the L boundary, the variable Elow is the lower end of the interval for a given symbol. The H boundary, which is omitted, may be recovered by performing: H=Elow+Erange, where the variable Erange is the length of the probability interval of the symbol. The variable Erange is the same as the previously described interval metric RANGE.
LPS range variable rLPS may be updated using a two dimensional array rLPS_table—64×4[64][4], as generally indicated by pointer 1905. This array is used to perform the update operation of: RANGELPS=RANGE×PLPS. In lieu of a multiplication, the update uses a look-up table. Arrow 1906 generally indicates the update of the MPS sub-range through the prefix operator “−=”, namely RANGEMPS may be determined by subtracting RANGELPS from the RANGE.
Initially, Elow or L is logic zeros prior to encoding, and thus the initial value of Erange is also zero. As generally indicated at 1907, if the current symbol is not an MPS, the L and Range values are updated. If a symbol to be encoded is an LPS, a LOW is adjusted as well as the RANGE is adjusted as indicated at 1907. Additionally, if a symbol to be encoded is an LPS, MPS is updated for a zero probability and a probability estimate is adjusted as being an LPS as indicated at 1918. If, however, a symbol to be encoded is not an LPS, a probability is adjusted as an MPS as indicated at 1919.
As generally indicated at 1918 and 1919, probability update is performed on bi_ct state. Note that the field “state” of the bi_ct data structure is the index into a probability table. If the symbol is not an MPS, the index points to a location of an LPS probability table as generally indicated at 1918. If the symbol is an MPS, the index points to a location in the MPS probability table, as generally indicated at 1919.
For each symbol that the function “biari_encode_symbol” processes, normalization loop 1922 may take up to seven iterations. Even though a listing 1900 is illustratively shown, it should be appreciated that listing 1900 may be instantiated in hardware to provide part of a CABAC encoder. Accordingly, it should be appreciated that as values such as LOW and RANGE are updated, such values may fall out of a bit range usable by such an encoder. Normalization loop 1922 is used to bring such values back within a bit range. Again, it should be appreciated that such normalization loop 1922 may take up to seven iterations, which when implemented in hardware may take multiple clock cycles per symbol. For RANGE less than QUARTER, outstanding bits are inserted for conditions, such as indicated at 1908 and 1909, within normalization loop 1922.
FIG. 20 is a program listing depicting an exemplary embodiment of a macro for writing bytes into the output stream, namely macro 2000, of the prior art. Macro 2000 is part of a JM source code reference as is known. Macro 2000, which defines insertion of outstanding bits (e.g., put_one_bit_plus_outstanding(b)) has either a logic ‘1’ or ‘0’ bit as its input parameter. The input parameter bit is then inserted directly into the output bit encoding stream as generally indicated at 2001. Macro 2000 then inserts sequentially a total of Ebits_to_follow 2003 number of bits into the output encoding stream. These inserted bits are all the bitwise complement of the original macro's input parameter bit. As generally indicated at 2002, Ebits_to_follow is a counter for outstanding bits. If this counter is greater than zero, and when LOW is greater than or equal to HALF and LOW is less than QUARTER, then the number of bits represented by the counter is inserted into the output encoding stream.
In addition to normalization loop 1922, the insertion of outstanding bits inside macro 2000 is an additional nested loop. This means that there may be several loops of macro 2000 per symbol. Even though there are conditions in which outstanding bits are not inserted within an iteration of normalization loop 1922, it should be appreciated that there is an accumulation and thus eventually all such outstanding bits are inserted into an output encoding stream. Thus, it should be appreciated that both macro 2000 and normalization loop 1922 may be significant impediments to real-time CABAC encoding.
As indicated above, for each binary input or bit to be encoded, there basically exist two potential bottlenecks which would limit real-time CABAC encoding for implementation in an FPGA, particularly for HD sequences. Thus, it would be desirable to have a more efficient normalization/renormalization procedure than that described above.